\subsection{Necessary condition: Theorem~\ref{thm:necessary.asymmetric}}
\label{sec:asym_necessary}

Let $k \in [n^{\frac{1}{10}},n^{\frac{9}{10}}]$ and $\alpha_i, \beta_i
\in [n^{-\frac{1}{100}},n^{\frac{1}{100}}]$, $i=1,2,\ldots,r$. Suppose
we are given a bipartite graph $G=(V,W,E)$ which is the union of
complete bipartite graphs $G_1,G_2,\ldots,G_r$ and has no bipartite
independent set of size $k \times k$, where $G_i=(V_i,W_i,E_i=V_i
\times W_i)$ with $|V_i| = m_i = \alpha_i (n/k)$ and $|W_i| = n_i =
\beta_i (n/k)$. As stated in Theorem~\ref{thm:necessary.asymmetric},
we let $p_i = \frac{\alpha_i}{\alpha_i + \beta_i}$ and $\ent(p_i) =
-p_i \log(p_i) - (1-p_i) \log(1-p_i)$. We wish to show that there is a
constant $D > 0$ such that
\[ \sum_{i \in X} \alpha_i \beta_i + \sum_{i \in \{1,2,\ldots,r\} \setminus X} (\alpha_i + \beta_i) \ent(p_i) \geq D k \log n \]
for every $X \subseteq \{1,2,\ldots,r\}$.

The proof is similar to the proof of
Thereom~\ref{thm:necessary.symmetric} and again we present the
argument for the case when $k=\sqrt{n}$. Fix a subset $X \subseteq
\{1,2,\ldots,r\}$. Our plan is to assume that the second term in the
LHS of the above inequality is small,
\[ \secondterm = \sum_{i \in \{1,2,\ldots,r\} \setminus X} (\alpha_i + \beta_i) \ent(p_i) \leq \frac{1}{100} k \log n,
\]
and from this conclude that the first term must be large,
\[  \firstterm = \sum_{i \in X} \alpha_i \beta_i \geq \frac{1}{100} k \log n.\]

Assume $\secondterm \leq \frac{1}{100} k \log n$. We will call a graph
$G_i$ whose index $i \in X$ as {\em marked}, and a graph $G_i$ whose
index $i \notin X$ as {\em unmarked}. As before, we will delete one of
the sides of each unmarked $G_i$ independently at random from the
vertex set of $G$.  However, since this time there are different
number of vertices on the two sides of $G_i$, we need to be more
careful and choose the deletion probabilities cleverly. We do so as
follows. For every unmarked $G_i$ independently, we delete all the
vertices in $W_i$ with probability $p_i$ and all its vertices in $V_i$
with the remaining probability $1-p_i$.

For a vertex $v \in V$, let $S_v$ be the set of $i \notin X$ such that
$v \in V_i$. Define $d_v$ to be the quantity $\sum_{i \in S_v}
\log(1/p_i)$. The probability that $v$ survives the random deletion
process is $2^{-d_v}$. Using the fact that $p_i =
\frac{\alpha_i}{\alpha_i + \beta_i}$ and plugging the expression for
$\ent(p_i)$ in the assumption that $\secondterm \leq \frac{1}{100} k
\log n$, we get
\[ \sum_{i \notin X} \left(\alpha_i \log (1/p_i) + \beta_i \log(1/(1-p_i)) \right) \leq \frac{1}{100} k \log n. \]
Multiplying both sides by $(n/k)$, this implies
\begin{equation}
\label{eq:left}
 \sum_{i \notin X} m_i \log (1/p_i)  \leq \frac{1}{100} n \log n, 
\end{equation}
and
\begin{equation}
\label{eq:right}
 \sum_{i \notin X} n_i \log (1/(1-p_i))  \leq \frac{1}{100} n \log n. 
\end{equation}
Since
\[ \sum_{v \in V} d_v = \sum_{i \notin X} m_i \log (1/p_i), \]
the average value of $d_v$ is at most $\frac{1}{100} \log n$, and by
Markov's inequality, at least $3n/4$ vertices $v \in V$ have their
$d_v$ at most $d =\frac{1}{25} \log n$. Moreover, since $\alpha_i,
\beta_i \in [n^{-1/100}, n^{1/100}]$, we have
\[ p_i \leq \frac{n^{1/100}}{n^{1/100} + n^{-1/100}}, \] 
and thus
\begin{eqnarray*}
 \frac{1}{p_i} & \geq & \frac{n^{1/100} + n^{-1/100}}{n^{1/100}} \\ 
               & = & \frac{1}{1 - \frac{n^{-1/100}}{n^{1/100} + n^{-1/100}}} \\
               & \geq & \exp\left(\frac{n^{-1/100}}{n^{1/100} + n^{-1/100}}\right) \\
               & \geq & \exp\left(\frac{1}{2} n^{-1/50}\right).
\end{eqnarray*}
The above implies $\log(1/p_i) \geq \frac{1}{2} n^{-1/50}$, which
combined with (\ref{eq:left}) yields
\[ \sum_{i \notin X} m_i \leq \frac{1}{50} n^{51/50} \log n. \]
Since
\[ \sum_{v \in V} |S_v| = \sum_{i \notin X} m_i, \]
the average value of $|S_v|$ is at most $\frac{1}{50} n^{1/50} \log
n$, and again by Markov's inequality, at least $3n/4$ vertices $v \in
V$ satisfies $|S_v| \leq d' = \frac{4}{50} n^{1/50} \log n$.

We focus on a set $V'$ of $n/2$ vertices $v \in V$ such that $d_v \leq
d$ and $|S_v| \leq d'$. If any vertex $v \in V'$ survives the first
deletion, we delete it further with probability $1-2^{-(d-d_v)}$, so
that the survival probability of each vertex in $V'$ is exactly
$2^{-d}= n^{-1/25}$.  Let $X$ be the set of vertices in $V'$ that
survive. Similarly, we define $W' \subseteq W$, and let $Y$ be the set
of vertices in $W'$ that survive.

\begin{claim}
With probability $1-o(1)$, $|X|, |Y| \geq \frac{n}{4}2^{-d}$.
\end{claim}

The proof of the claim is exactly like the previous time. For $v \in
V'$, we let $I_v$ be the indicator variable for the event that $v$
survives in $X$. Then, $\Pr[I_v=1]= 2^{-d} = n^{-1/25}$ for all $v \in
V'$.  Furthermore, $I_v$ and $I_{v'}$ are dependent precisely if there
is a common unmarked $G_i$ such that both $v, v' \in V_i$. Thus, any
one $I_v$ is dependent on at most $\Delta = |S_v| \times \max\{m_i: i
\notin X\} \leq (4/50) n^{1/50} \log n n^{1/100} (n/k) = (4/50)
n^{53/100} \log n$ such events (recall $k = \sqrt{n}$). Now we have
\begin{eqnarray*}
\E[|X|] & = & \sum_{v \in V'} I_v = \frac{n}{2}2^{-d} = \frac{1}{2}n^{24/25};\\
\var[|X|] & \leq & E[|X|] \Delta.
\end{eqnarray*}
By Chebyshev's inequality, the probability that $|X|$ is 
less than $\frac{\E[|X|]}{2}$ is at most 
\[ \frac{4\var[X]}{\E[|X|]^2} \leq \frac{4 \Delta}{\E[|X|]} = o(1). \]
A similar calculation can be done for $|Y|$.  (End of Claim.)

Since no unmarked $G_i$ has any edge between $X$ and $Y$, the marked
$G_i$'s must provide enough edges to avoid all
independent sets of size $k \times k$ between $X$ and $Y$. As in the proof of
Theorem~\ref{thm:necessary.symmetric}, we can argue that an edge of a
marked $G_i$ survives in $X \times Y$ with probability at most $2^{-2d}$. Thus the
expected number of edges supplied between $X$ and $Y$ by marked
$G_i$'s is at most
\[ \sum_{i \in X} m_i n_i 2^{-2d} = \sum_{i \in X} \alpha_i \beta_i (n/k)^2 2^{-2d} = \firstterm \times (n/k)^2 2^{-2d}, \]
and by Markov's inequality with probability $1/2$ it is at most twice
its expectation. Thus the event where both $X$ and $Y$ are of size at
least $\frac{n}{4} 2^{-d}$ and the number of edges connecting them is
at most $\firstterm \times (n/k)^2 2^{-2d}$ occurs with positive
probability. From (\ref{eq:kst-edges}), this number of edges
must be at least $\frac{1}{3} \frac{24}{25} \frac{(n2^{-d})^2}{16k}
\log n$. (Note that $\frac{1}{3}$ suffices as the constant in
(\ref{eq:kst-edges}) when $|X|, |Y| \geq \frac{n^{24/25}}{4}$
and $k = \sqrt{n}$.) Thus we get
\[ \firstterm \geq \frac{1}{100} k \log n. \]
